package com.sinaapp.gavinzhang.jianzhioffer;

import java.util.ArrayList;
import java.util.List;

/**
 * 从中序和前序得到二叉树
 * Created by gavin on 15-9-3.
 */
public class LastRoot {
    public static void main(String[] args)
    {
        int[] xiangen = {1,2,4,3,5,6};
        int[] zhonggen = {4,2,1,5,3,6};
        //System.out.println(Arrays.binarySearch(zhonggen,0,3,2));
        Node root = shun(xiangen,zhonggen,0,xiangen.length-1);
        ArrayList<Integer> list = new ArrayList<Integer>();
        Integer[] hougen = new Integer[xiangen.length-1];
        getHougen(list, root);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }

    }

    public static Node shun(int[] xiangen,int[] zhonggen,int zhongLow,int zhongHigh) {
        if (zhongLow > zhongHigh) return null;
        if (zhongHigh >= zhonggen.length) return null;
        if (zhongLow < 0) return null;
        int i = 0;
        for (i = 0; i < xiangen.length; i++) {
            if (find(zhonggen, zhongLow, zhongHigh, xiangen[i]) >= 0) break;
        }
        if (find(zhonggen, zhongLow, zhongHigh, xiangen[i]) < 0) return null;
        Node root = new Node();
        root.data = xiangen[i];
        root.left = shun(xiangen, zhonggen, zhongLow, find(zhonggen, 0, zhonggen.length - 1, root.data) - 1);
        root.right = shun(xiangen, zhonggen, find(zhonggen, 0, zhonggen.length - 1, root.data) + 1, zhongHigh);
        return root;
    }

    public static int find(int[] tmp ,int fromIndex,int toIndex,int key)
    {
        for (int i = fromIndex; i <= toIndex; i++) {
            if (tmp[i] == key)return i;
        }
        return -1;
    }
    public static List<Integer> getHougen(List<Integer> list,Node root)
    {
        if (root == null)return list;
        getHougen(list,root.left);
        getHougen(list, root.right);
        list.add(root.data);
        return list;
    }
    static class Node {
        public Node left;
        public Node right;
        public int data;
    }


}

